home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3701 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.2 KB  |  81 lines
  1. Newsgroups: comp.lang.c
  2. Path: mxsld2.pd.infn.it!LORETI
  3. From: loreti@mxsld2.pd.infn.it (Maurizio Loreti)
  4. Subject: Re: Fastest way to computer log(base2) of x?
  5. X-Nntp-Posting-Host: mxsld2.pd.infn.it
  6. Message-ID: <DM0AKu.A2H@news.cern.ch>
  7. Sender: news@news.cern.ch (USENET News System)
  8. Reply-To: loreti@mxsld2.pd.infn.it
  9. Organization: I.N.F.N. Padova - CDF/CMS VAXcluster
  10. References: <4e61iu$p6e@villa.fc.net> <4e6p7t$1n72@cymbal.aix.calpoly.edu> <4e8r54$n8q@ns.RezoNet.NET>,<4e9bl4$3ccp@cymbal.aix.calpoly.edu>
  11. Date: Tue, 30 Jan 1996 18:12:28 GMT
  12.  
  13. In article <4e9bl4$3ccp@cymbal.aix.calpoly.edu>, you write:
  14. >...
  15. >int left_most_bit (int k) {
  16. >   unsigned posn = 0, mask = 0x80000000;
  17. >
  18. >   while (!(k & mask)) {
  19. >      mask >>= 1;
  20. >      posn++;
  21. >   }
  22. >   return posn;
  23. >}
  24. >+----------------------------------------------------+
  25.  
  26. A few comments...
  27.  
  28. - You are right that the overhead of a binary search is not worth
  29.   with, and that a linear search is faster.
  30. - It is better to make k an unsigned int, as usual when bit operations
  31.   are performed; however that is not essential.
  32. - 'mask' is initialised to 0x80000000 assuming an int is 32 bits; this
  33.   is not portable.  You could #include <limits.h> and set mask to
  34.   ~(UNIT_MAX >> 1) to do that.
  35. - As it is, the function returns 0 (and not 31) if the MSB bit is set...
  36.   bits are usually numbered starting from 0 (the LSB).
  37. - As it is, does not handle k=0.
  38.  
  39. Try the following:
  40.  
  41. FNALP> type foo.c
  42. #include <stdio.h>
  43. #include <limits.h>
  44.  
  45. int msb(unsigned int);
  46.  
  47. int main()
  48. {
  49.   unsigned int array[] = {0x0, 0x1, 0x10, UINT_MAX};
  50.   size_t index;
  51.  
  52.   for (index = 0;   index < sizeof(array)/sizeof(array[0]);  ++index)
  53.     printf("MSB set in %X is %d\n", array[index], msb(array[index]));
  54.  
  55.   return 0;
  56. }
  57.  
  58. int msb(            /* Returns the MSB bit set in u, or -1 if u is 0 */
  59.   unsigned int u    /* MLO 1996-01-30 */
  60. ){
  61.   int retval = -1;
  62.  
  63.   while (u) {
  64.     ++retval;
  65.     u >>= 1;
  66.   }
  67.   return retval;
  68. }
  69. FNALP> cc foo
  70. FNALP> link foo
  71. FNALP> run foo
  72. MSB set in 0 is -1
  73. MSB set in 1 is 0
  74. MSB set in 10 is 4
  75. MSB set in FFFFFFFF is 31
  76.  
  77. Hope that helps...  Comments welcome.
  78. --
  79. Maurizio Loreti                       http://mvxpd5.pd.infn.it/wwwcdf/mlo.html
  80. Un. of Padova, Dept. of Physics - Padova, Italy          loreti@padova.infn.it
  81.